In an asynchronous computer system, two or more autonomous units may request access to a common resource (e.g. a memory) within a short time of one another. If the requests are sufficiently separated in time, a first request can be recognized and serviced before a second request is received. However, in highly parallel processing systems where a number of processes execute simultaneously, it is a very common occurrence that multiple processes request access to the common resource at substantially the same time (e.g., within a few clock cycles of one another).
To handle the overlapping requests, an arbiter determines how to allocate the resource to each of the requesting units (allocating the resource is also referred to as servicing the request, or granting access to the resource). Generally, the time needed for the arbiter to decide which process should get access to the shared resource should be as short as possible, since a long decision time adds directly to access time, increasing client read latency.
The arbiter may allocate access to the shared resource using one or more known schemes. In a predetermined priority scheme, processes are assigned predetermined levels of priority, and the arbiter generally prefers a higher priority process over a lower priority process. In a time-based scheme, the arbiter generally prefers a process that generated a request long ago, over a process that generated a request only a short time ago.
However, known schemes for arbitration may be suboptimal in several regards.